package com.cute.leetcode.editor.cn;
import java.util.Scanner;
public class HJ16GouWuDan {
    /**
     * 很棒的一道0-1背包问题
     * 状态多一些的01背包问题，每个商品包含价值和权重，分别进行保存
     * http://www.nowcoder.com/practice/f9c6f980eeec43ef85be20755ddbeaf4
     */
    public static void main(String[] args) {
        String[] split = "225.123.14.54".split("\\.");
        Scanner in = new Scanner(System.in);
        int N = in.nextInt() / 10; //价格，由于金额是10的倍数，可以这样处理，节省空间
        int m = in.nextInt();// 总物品数目
        int[][] prices = new int[N + 1][3];// 存储价格
        int[][] weights = new int[m + 1][3];// 存储权重
        in.nextLine();
        for (int i = 1; i <= m; i++){
            int v = in.nextInt() / 10;// 需要的钱
            int p = in.nextInt() * v;// 钱*重要度
            int q = in.nextInt();
            in.nextLine();
            if (q == 0){// 主件直接加就行
                prices[i][0] = v;
                weights[i][0] = p;
            }else if (prices[q][1] == 0){// 从件先试着赋值到主件的第一个位置去
                prices[q][1] = v;
                weights[q][1] = p;
            }else{// 1号有从件后赋值到从件2
                prices[q][2] = v;
                weights[q][2] = p;
            }
        }
        int[] dp = new int[N + 1];// 压缩空间到1维
        for (int i = 1; i <= m; i++){// 遍历所有物品
            for (int j = N; j >= 1; j--){// 从后向前遍历防止出错
                //分为四种情况：只放主，放主1+从1，放主2+从2，放主+从1+从2
                int p1 = prices[i][0];// 主件金额，从件都为0的
                int w1 = weights[i][0];// 主件权重
                int p2 = prices[i][1];// 从件1金额
                int w2 = weights[i][1];// 从件1权重
                int p3 = prices[i][2];// 从件2金额
                int w3 = weights[i][2];// 从件2权重
                if (j - p1 >= 0) dp[j] = Math.max(dp[j], dp[j-p1] + w1);
                if (j - p1 - p2 >= 0) dp[j] = Math.max(dp[j], dp[j - p1 - p2] + w1 + w2);
                if (j - p1 - p3 >= 0) dp[j] = Math.max(dp[j], dp[j - p1 - p3] + w1 + w3);
                if (j - p1 -p2 - p3 >= 0) dp[j] = Math.max(dp[j], dp[j - p1 -p2 - p3] + w1 + w2 + w3);
            }
        }
        System.out.println(dp[N] * 10);
    }
}
/*
42.53.252.112~255.0.0.0
166.237.7.68~255.0.0.0
136.3.73.64~255.255.0.0
204.29.136.133~255.255.0.245
195.30.208.94~255.255.0.213
154.253.86.183~255.200.255.0
94.164.187.131~255.255.0.0
167.79.164.186~255.0.0.0
194.172.2.64~255.255.0.0
210.212.79.137~255.255.255.42
143.151.137.40~255.255.255.255
184.145.79.157~255.0.0.0
100.214.131.51~255.255.255.255
233.10.182.98~255.0.0.125
99.184.165.228~255.0.0.82
*/